import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 定义公共类 BinaryTree，表示二叉树结构
public class BinaryTree {

    // 静态内部类 TreeNode，表示二叉树的节点
    static class TreeNode {
        public char val;         // 节点存储的字符值（如 'A', 'B' 等）
        public TreeNode left;    // 左子节点指针
        public TreeNode right;   // 右子节点指针

        // 构造函数，初始化节点值，左右子节点默认为 null
        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 创建并返回一个预定义结构的二叉树
    public TreeNode createTree() {
        // 创建所有节点，节点值从 'A' 到 'H'
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        // 构建树结构
        A.left = B;   // A 的左子节点是 B
        A.right = C;  // A 的右子节点是 C
        B.left = D;   // B 的左子节点是 D
        B.right = E;  // B 的右子节点是 E
        C.left = F;   // C 的左子节点是 F
        C.right = G;  // C 的右子节点是 G
        E.right = H;  // E 的右子节点是 H（注意：E 的左子节点未设置，默认为 null）

        return A; // 返回根节点 A
    }

    // 前序遍历：根 -> 左 -> 右
    public void preOrder(TreeNode root) {
        if (root == null) return;       // 递归终止条件：空节点
        System.out.print(root.val + " "); // 访问根节点
        preOrder(root.left);             // 递归遍历左子树
        preOrder(root.right);            // 递归遍历右子树
    }

    // 中序遍历：左 -> 根 -> 右
    public void inOrder(TreeNode root) {
        if (root == null) return;        // 递归终止条件：空节点
        inOrder(root.left);              // 递归遍历左子树
        System.out.print(root.val + " "); // 访问根节点
        inOrder(root.right);             // 递归遍历右子树
    }

    // 后序遍历：左 -> 右 -> 根
    public void postOrder(TreeNode root) {
        if (root == null) return;         // 递归终止条件：空节点
        postOrder(root.left);            // 递归遍历左子树
        postOrder(root.right);           // 递归遍历右子树
        System.out.print(root.val + " ");  // 访问根节点
    }

    // 成员变量：用于记录节点个数（遍历思路）
    public int nodeSize;

    /**
     * 遍历思路获取节点个数
     * 时间复杂度：O(n)，每个节点访问一次
     */
    public void getNodeSize1(TreeNode root) {
        nodeSize = 0;          // 重置计数器
        if (root == null) return;
        nodeSize++;            // 当前节点计数
        getNodeSize1(root.left);   // 递归左子树
        getNodeSize1(root.right);  // 递归右子树
    }

    /**
     * 子问题思路获取节点个数
     * 递归公式：节点数 = 左子树节点数 + 右子树节点数 + 1
     * 时间复杂度：O(n)
     */
    public int getNodeSize2(TreeNode root) {
        if (root == null) return 0;
        return getNodeSize2(root.left) + getNodeSize2(root.right) + 1;
    }



    /**
     * 遍历思路获取叶子节点个数
     * 叶子节点条件：left 和 right 均为 null
     */
    // 成员变量：用于记录叶子节点个数（遍历思路）
    public int leafCount;
    public void getLeafNodeCount1(TreeNode root) {
        leafCount = 0;        // 重置计数器
        if (root == null) return;
        if (root.left == null && root.right == null) {
            leafCount++;      // 当前节点是叶子节点
        }
        getLeafNodeCount1(root.left);   // 递归左子树
        getLeafNodeCount1(root.right);  // 递归右子树
    }

    /**
     * 子问题思路获取叶子节点个数
     * 递归公式：叶子数 = 左子树叶子数 + 右子树叶子数
     */
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;  // 当前节点是叶子
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    /**
     * 获取第 K 层节点的个数
     * 递归公式：k 层节点数 = 左子树 (k-1) 层节点数 + 右子树 (k-1) 层节点数
     */
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;  // 当前层是第 k 层
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    /**
     * 计算二叉树的高度（方法1）
     * 递归公式：高度 = max(左子树高度, 右子树高度) + 1
     */
    public int getHeight1(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight1(root.left);
        int rightHeight = getHeight1(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 计算二叉树的高度（方法2，等价于方法1）
     * 使用三元运算符简化代码
     */
    public int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight2(root.left);
        int rightHeight = getHeight2(root.right);
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }

    /**
     * 查找值为 key 的节点（递归实现）
     * 先查根，再递归左子树，最后递归右子树
     */
    public TreeNode find(TreeNode root, char key) {
        if (root == null) return null;       // 终止条件
        if (root.val == key) return root;     // 当前节点找到
        TreeNode leftResult = find(root.left, key);  // 递归左子树
        if (leftResult != null) return leftResult;   // 左子树找到则返回
        return find(root.right, key);         // 否则递归右子树
    }

    /**
     * 判断两棵树是否相同（结构和值）
     * 递归条件：
     * 1. 根节点值相同
     * 2. 左子树相同
     * 3. 右子树相同
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 结构检查：一个空一个非空 -> 不同
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        // 都为空 -> 相同
        if (p == null && q == null) return true;
        // 值不同 -> 不同
        if (p.val != q.val) return false;
        // 递归检查左右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /**
     * 判断 subRoot 是否是 root 的子树
     * 遍历 root 的每个节点，判断是否与 subRoot 相同
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;  // 递归终止条件
        if (isSameTree(root, subRoot)) return true;  // 当前节点开始的子树匹配
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); // 递归左右子树
    }

    /**
     * 翻转二叉树（镜像反转）
     * 递归交换每个节点的左右子节点
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 交换左右子节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        // 递归处理左右子树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /**
     * 判断是否是平衡二叉树（方法1）
     * 平衡条件：
     * 1. 左右子树高度差 <= 1
     * 2. 左右子树都是平衡的
     * 缺点：重复计算高度，时间复杂度 O(n^2)
     */
    public boolean isBalanced1(TreeNode root) {
        if (root == null) return true;
        int leftHeight = getHeight1(root.left);
        int rightHeight = getHeight1(root.right);
        return Math.abs(leftHeight - rightHeight) <= 1
                && isBalanced1(root.left)
                && isBalanced1(root.right);
    }

    /**
     * 判断是否是平衡二叉树（方法2，优化）
     * 自底向上计算高度，若子树不平衡返回 -1
     * 时间复杂度 O(n)
     */
    public boolean isBalanced2(TreeNode root) {
        return maxDepth(root) >= 0;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = maxDepth(root.left);
        if (leftHeight < 0) return -1;  // 左子树不平衡
        int rightHeight = maxDepth(root.right);
        if (rightHeight < 0) return -1; // 右子树不平衡
        if (Math.abs(leftHeight - rightHeight) > 1) return -1; // 当前树不平衡
        return Math.max(leftHeight, rightHeight) + 1; // 返回当前树高度
    }

    /**
     * 判断是否是对称二叉树
     * 对称条件：左右子树镜像对称
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricChild(root.left, root.right); // 检查左右子树
    }

    private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        // 结构检查
        if ((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
            return false;
        }
        if (leftTree == null && rightTree == null) return true;
        // 值检查
        if (leftTree.val != rightTree.val) return false;
        // 递归检查镜像对称
        return isSymmetricChild(leftTree.left, rightTree.right)
                && isSymmetricChild(leftTree.right, rightTree.left);
    }

    /**
     * 层序遍历（广度优先遍历）
     * 使用队列辅助实现
     */
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // 根节点入队
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            // 左子节点入队
            if (cur.left != null) queue.offer(cur.left);
            // 右子节点入队
            if (cur.right != null) queue.offer(cur.right);
        }
    }

    /**
     * 分层返回层序遍历结果（返回二维列表）
     * 每层节点值存储在一个子列表中
     */
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();  // 当前层节点数
            List<Character> level = new ArrayList<>();
            while (size-- > 0) {      // 遍历当前层
                TreeNode cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            ret.add(level);  // 添加当前层结果
        }
        return ret;
    }
}